import java.util.Arrays;
import java.util.HashMap;
import java.util.Map;
import java.util.Objects;

class Person{
    public String ID;

    public Person(String ID) {
        this.ID = ID;
    }

    @Override
    public String toString() {
        return "Person{" +
                "ID='" + ID + '\'' +
                '}';
    }

    @Override
    public boolean equals(Object o) {
        if (this == o) return true;
        if (o == null || getClass() != o.getClass()) return false;
        Person person = (Person) o;
        return Objects.equals(ID, person.ID);
    }

    @Override
    public int hashCode() {
        return Objects.hash(ID);
    }
}
public class HashTest {
    public static int func(int key) {
        int f1 = 0;
        int f2 = 1;
        int f3 = -1;
        while (f3 < key) {
            f3 = f1 + f2;
            if(f3 > key) {
                break;
            }
            f1 = f2;
            f2 = f3;
        }
        int a = f2;
        int b = f1+f2;
        int ret1 = key-a;
        int ret2 = b-key;
        if(ret1 > ret2) {
            return ret2;
        } else {
            return ret1;
        }
    }
    public static String func(StringBuilder str) {
        int count = 0;
        for (int i = 0; i < str.length(); i++) {
            if(str.charAt(i) == ' ') {
                count++;
            }
        }
        int new_length = str.length()+2*count;
        int old_index = str.length()-1;
        int new_index = new_length-1;
        str.setLength(new_length);
        while (old_index >= 0 && new_index >= 0) {
            if(str.charAt(old_index) == ' ') {
                str.setCharAt(new_index--,'0');
                str.setCharAt(new_index--,'2');
                str.setCharAt(new_index--,'%');
                old_index--;
            } else {
                str.setCharAt(new_index--,str.charAt(old_index));
                old_index--;
            }
        }
        return str.toString();
    }
    public static boolean Find(int target, int [][] array) {
        int i = 0;
        int j = array[0].length-1;
        while (i < array.length && j >= 0) {
            if(array[i][j] > target) {
                j--;
            }else if (array[i][j] < target) {
                i++;
            }else {
                return true;
            }
        }
        return false;
    }

    public static void main(String[] args) {
        int[][] array = {{1,1}};
        int a = 2;
        boolean f = Find(a,array);
        System.out.println(f);
    }
    public static void main3(String[] args) {
        String str = "ha ha ha ha h";
        String str1 = str.replace(" ","%20");
        System.out.println(str1);
    }
    public static void main2(String[] args) {
        int ret = func(15);
        System.out.println(ret);
    }
    public static void main1(String[] args) {
        Person person = new Person("123");
        Person person1 = new Person("123");
        System.out.println(person.hashCode());
        System.out.println(person1.hashCode());
        Map<String,Integer> map = new HashMap<>();
        map.put("1",1);
    }
}
